package com.example;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019/2/13
 * @Description: 类描述
 **/
public class 排序 {

    public static void main(String[] args) {
//        冒泡排序();
//        快速排序();
//        选择排序();
//        插入排序();
        希尔算法();

    }

    /**
     * 希尔排序的原理:根据需求，如果你想要结果从大到小排列，它会首先将数组进行分组，然后将较大值移到前面，较小值
     * 移到后面，最后将整个数组进行插入排序，这样比起一开始就用插入排序减少了数据交换和移动的次数，可以说希尔排序是加强
     * 版的插入排序
     * 拿数组5, 2, 8, 9, 1, 3，4来说，数组长度为7，当increment为3时，数组分为两个序列
     * 5，2，8和9，1，3，4，第一次排序，9和5比较，1和2比较，3和8比较，4和比其下标值小increment的数组值相比较
     * 此例子是按照从大到小排列，所以大的会排在前面，第一次排序后数组为9, 2, 8, 5, 1, 3, 4
     * 第一次后increment的值变为3/2=1,此时对数组进行插入排序，
     * 实现数组从大到小排
     */
    public static void 希尔算法() {
        int[] numbers = {45, 32, 56, 76, 89, 12, 43, 55, 566, 87};
        int size = numbers.length;

        int j = 0;
        int temp = 0;
        for (int increment = size / 2; increment > 0; increment /= 2) {
            for (int i = increment; i < size; i++) {
                temp = numbers[i];
                for (j = i; j >= increment; j -= increment) {
                    if (temp > numbers[j - increment]) {
                        numbers[j] = numbers[j - increment];
                    } else {
                        break;
                    }
                }
                numbers[j] = temp;
            }
        }


        for (int i = 0; i < size; i++) {
            System.out.print(numbers[i] + " ");
        }
    }

    /**
     * 插入排序
     * <p>
     * 从第一个元素开始，该元素可以认为已经被排序
     * 取出下一个元素，在已经排序的元素序列中从后向前扫描
     * 如果该元素（已排序）大于新元素，将该元素移到下一位置
     * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
     * 将新元素插入到该位置中
     * 重复步骤2
     */
    public static void 插入排序() {
        int[] numbers = {45, 32, 56, 76, 89, 12, 43, 55, 566, 87};
        int size = numbers.length;
        int temp = 0;

        int j = 0;

        for (int i = 0; i < size; i++) {
            temp = numbers[i];
            //假如temp比前面的值小,则将前面的值往后移
            for (j = i; j > 0 && temp < numbers[j - 1]; j--) {
                numbers[j] = numbers[j - 1];
            }
            numbers[j] = temp;
        }

        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }

    }

    /**
     * 选择排序算法
     * 在未排序序列中找到最小元素，存放到排序序列的起始位置
     * 再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。
     * 以此类推，直到所有元素均排序完毕。
     */
    public static void 选择排序() {
        int[] numbers = {45, 32, 56, 76, 89, 12, 43, 55, 566, 87};
        int size = numbers.length;
        //中间变量
        int temp = 0;
        for (int i = 0; i < size; i++) {
            //待确定位置
            int k = i;
            //选择出应该在第i个位置的数
            for (int j = size - 1; j > i; j--) {
                if (numbers[j] < numbers[k]) {
                    k = j;
                }
            }
            //交换两个数
            temp = numbers[i];
            numbers[i] = numbers[k];
            numbers[k] = temp;
        }

        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }

    }

    /**
     * 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
     */
    public static void 快速排序() {
        int[] numbers = {45, 32, 56, 76, 89, 12, 43, 55, 566, 87};
        //查看数组是否为空
        if (numbers.length > 0) {
            quickSort(numbers, 0, numbers.length - 1);
        }
        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }
    }

    public static void quickSort(int[] numbers, int low, int high) {
        if (low < high) {
            //将numbers数组进行一分为二
            int middle = getMiddle(numbers, low, high);
            //对低字段表进行递归排序
            quickSort(numbers, low, middle - 1);
            //对高字段表进行递归排序
            quickSort(numbers, middle + 1, high);
        }
    }

    public static int getMiddle(int[] numbers, int low, int high) {
        //数组的第一个作为中轴
        int temp = numbers[low];
        while (low < high) {
            while (low < high && numbers[high] > temp) {
                high--;
            }
            //比中轴小的记录移到低端
            numbers[low] = numbers[high];
            while (low < high && numbers[low] < temp) {
                low++;
            }
            //比中轴大的记录移到高端
            numbers[high] = numbers[low];
        }
        //中轴记录到尾
        numbers[low] = temp;
        //返回中轴的位置
        return low;
    }

    /**
     * 冒泡排序
     * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
     * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
     * 针对所有的元素重复以上的步骤，除了最后一个。
     * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
     */
    public static void 冒泡排序() {
        int[] a = {45, 32, 56, 76, 89, 12, 43, 55, 566, 87};
        //当前最大值
        int max;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length - (i + 1); j++) {
                if (a[j] > a[j + 1]) {
                    max = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = max;
                }
            }
        }
        System.out.print("从小到大：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
        int[] b = {45, 32, 56, 76, 89, 12, 43, 55, 566, 87};
        //当前最小值
        int min;
        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b.length - (i + 1); j++) {
                if (b[j] < b[j + 1]) {
                    min = b[j];
                    b[j] = b[j + 1];
                    b[j + 1] = min;
                }
            }
        }
        System.out.print("从大到小：");
        for (int i = 0; i < b.length; i++) {
            System.out.print(b[i] + " ");
        }
    }
}
